<?php

// Algo to find the k-th element in two sorted array combined

require_once 'util.php';

$A = generateRandomArray( 0, 99, 3 );
$B = generateRandomArray( 0, 99, 5 );

sort( $A );
sort( $B );

echo implode(' ', $A);
echo "<br/>";

echo implode(' ', $B);
echo "<br/>";

kthElementInArrasy(4, $A, $B);

// Simple O(k) algo, comparing elements silimar to the merge sort without actually merging
function kthElementInArrasy( $k, $A, $B ){
	$sizeA = count( $A );
	$sizeB = count( $B );
	if( $sizeA + $sizeB < $k ){
		// OOPS
		return null;
	}
	
	$i = 0;
	$j = 0;
	$cur = 0;
	while( $i + $j < $k ){
		
		// When either array exhausted
		if( $i >= $sizeA ){
			$cur = $B[$j];
			$j++;
			continue;
		}
		if( $j >= $sizeB ){
			$cur = $A[$i];
			$i++;
			continue;
		}
		
		// Counting
		if( $A[$i] <= $B[$j] ){
			// $i + $j th value is $A[$i]
			$cur = $A[$i];
			$i++;						
		}
		else {
			// $i + $j th value is $B[$j]
			$cur = $B[$j];
			$j++;
		}
	}
	
	echo "$k -th value is $cur<br/>";
}

/**
 * There is a faster method, referencing binary search in sorted array
 * Maintaining the constrain $i + $j == $k - 1
 * Search $A and $B
 * 
 * $A[] $A[$i-1] $A[$i] $A[] ...
 *              |
 *             $B[$j] $B[] $B[] $B[] ...
 * 
 * Imagine the vertical line stays at $i+$j = $k-1. If move $A to the left, $B must move to the right.
 * When matched, it is either:
 * $A[$i-1] < $B[$j] < $A[$i] or $B[$j-1] < $A[$i] < $B[$j]
 * else  
 * when $A[$i] < $B[$j] => increase $i, look into $A[$i+1, $m-1] and $B[0, $j-1]
 * when $A[$i] > $B[$j] => decrease $i, look into $A[0, $i-1] and $B[$j+1, $n-1]
 * ($j will move accordingly, due to the constrain)
 * 
 * How much we move?
 * If we move like Jagger, I mean, like binary search, the algo will become O(log$m + log$n)
 */
function kthElementInArrasyBinary($k, $A, $B){
	
}